/*
     给定数组array = {1, 3, 4, 5, 6, 7, 8, 9, 10, 11}，对数组进行二分查找，查找数字6。
     要求： 找到返回素索引
           找不到返回-1
  */

package com.diudiu.BinarySearch;

public class Test01 {
    public static void main(String[] args) {
        // 定义一个数组
        int[] array = {1, 3, 4, 5, 6, 7, 8, 9, 10, 11};

        // 调用myBinarySearch方法，传入数组和要查找的数，返回查找的索引
        int index = myBinarySearch(array, 6);
        System.out.println(index);
    }

    private static int myBinarySearch(int[] array, int i) {
        // 定义一个低位，初始值为0
        int low = 0;

        // 定义一个高位，初始值为数组的长度减1
        int high = array.length - 1;

        // 当低位小于高位时，循环执行
        while (low <= high) {
            // 定义一个中间变量，防止计算时溢出
            int middle = (low + high) >>> 1;
            // 如果中间变量大于要查找的数，说明要查找的数在低位到中间变量之间，将高位设置为中间变量减1
            if (array[middle] > i) {

                high = middle - 1;
                // 如果中间变量小于要查找的数，说明要查找的数在中间变量到高位之间，将低位设置为中间变量加1
            } else if (array[middle] < i) {

                low = middle + 1;
                // 如果中间变量等于要查找的数，返回中间变量的索引
            } else {
                return middle;
            }
        }
        // 如果没有找到要查找的数，返回-1
        return -1;
    }
}
